#include	<stdio.h>
#include	<stdlib.h>
#include	<string.h>

#include	"tinyda.h"


//
// Keyset.
//


// Macros.


// Initial size of a hash table (1 << HASH_MIN).
#define		HASH_MIN	8


// Structures.


// Text file which includes keys.
typedef		struct DAFile
{
	int		size;	// File size.
	int		pos;	// Position of byte which will be processed next.
	char	buf[];	// Buffer.
}	DAFile, *hDAFile;

// Key.
typedef		struct DAKey	*hDAKey;
typedef		struct DAKey
{
	hDAKey	next;	// Next key.
	int		rec;	// Record size.
	int		len;	// Key length.
	int		idx;	// Index of corresponding leaf node.
	int		depth;	// Depth of corresponding leaf node.
					// The depth of children of root is 0.
	int		unify;	// This key should be unified or not.
	char	s[];	// Key string.
}	DAKey;

// Keyset.
typedef		struct DASet
{
	hDAKey	*tbl;	// Hash table.
	int		nbit;	// Size of hash table.
	int		mask;	// Mask to get hash value (mask = size - 1).
	int		n;		// Number of keys.
}	DASet;

// Sorted keyset.
typedef		struct DASort
{
	int		n;		// Number of keys.
	int		type;	// This flag indicates if the keyset includes keys which
					// have different size of records.
	int		max;	// Maximum record size.
	int		depth;	// Maximum key length.
	hDAKey	key[];	// Pointers to keys.
}	DASort, *hDASort;


// Functions to process strings.


// Calculate the length of a string.
static	int		DAStr_Len( const char *s )
{
	const char	*p = s;

	while ( *p != '\0' )
		p++;

	return	( int )( p - s );
}

// Copy a string (src) to a buffer (dst).
static	void	DAStr_Copy( char *dst, const char *src )
{
	do
		*dst++ = *src;
	while ( *src++ != '\0' );
}

// Compare two strings.
// If a == b, this function returns 0
// If a < b, this function returns a negative value,
// and if a > b, this function returns a positive value.
static	int		DAStr_Cmp( const char *a, const char *b )
{
	while ( *a != '\0' && *a == *b )
		a++, b++;

	return	( unsigned char )*a - ( unsigned char )*b;
}

// Compare two strings.
// If a == b, this function returns a pointer to the next byte of the end of
// string, and if a != b, this function returns NULL.
static	char	*DAStr_Match( char *a, const char *b )
{
	while ( *a != '\0' && *a == *b )
		a++, b++;

	return	( *a == *b ) ? ( a + 1 ) : NULL;
}

// Compare two strings.
// If the 1st argument is one of the prefixes of the 2nd argument,
// this function returns a pointer to the next byte of the end of string.
// Also, 2nd argument is changed in this function.
static	char	*DAStr_Prefix( char *a, const char **b )
{
	// Checks if the first bytes are same.
	if ( *a != **b )
		return	NULL;

	while ( *a != '\0' && *a == **b )
		a++, ++*b;

	return	( *a == '\0' ) ? ( a + 1 ) : NULL;
}


// Creation and destruction of a key.


// Initialize a key.
static	void	DAKey_Init( hDAKey h, const char *key, int len )
{
	memset( h, 0, sizeof( *h ) );

	h->next = NULL;
	h->len = len;

	DAStr_Copy( h->s, key );
}

// Create a key.
static	hDAKey	DAKey_Create( const char *key )
{
	int		len;
	hDAKey	h;

	len = DAStr_Len( key );
	if ( ( h = ( hDAKey )malloc( sizeof( *h ) + len + 1 ) ) != NULL )
		DAKey_Init( h, key, len );

	return	h;
}

// Clear a key.
static	void	DAKey_Finish( hDAKey h )
{
}

// Destroy a key.
static	void	DAKey_Delete( hDAKey h )
{
	DAKey_Finish( h );
	free( h );
}


// Creation and destruction of a keyset.


// Initialize a keyset.
static	void	DASet_Init( hDASet h )
{
	memset( h, 0, sizeof( *h ) );
}

// Create a keyset.
static	hDASet	DASet_Create( void )
{
	hDASet	h;

	if ( ( h = ( hDASet )malloc( sizeof( *h ) ) ) != NULL )
		DASet_Init( h );

	return	h;
}

// Clear a keyset.
static	void	DASet_Finish( hDASet h )
{
	int		i, max;
	hDAKey	key, next;

	if ( h->tbl != NULL )
	{
		for ( i = 0, max = 1 << h->nbit; i < max; i++ )
		{
			for ( key = h->tbl[i]; key != NULL; key = next )
			{
				next = key->next;
				DAKey_Delete( key );
			}
		}
		free( h->tbl );
	}
}

// Destroy a keyset.
static	void	DASet_Delete( hDASet h )
{
	DASet_Finish( h );
	free( h );
}


// Hashing.


// Calculate a hash value from a key.
static	int		DASet_Hash( const char *key )
{
	unsigned	val = 0;

	while ( *key != '\0' )
		val += ( val << 5 ) + ( unsigned char )*key++;

	return	( int )( val >> 1 );
}

// Move keys from an old position to a new position.
static	void	DASet_Divide( hDASet h, int nbit )
{
	int		i, max, mask, val;
	hDAKey	*p, key;

	max = 1 << h->nbit;
	mask = ( 1 << nbit ) - 1;

	for ( i = 0; i < max; i++ )
	{
		// Initialize expanded area.
		h->tbl[ max + i ] = NULL;
		for ( p = &h->tbl[i]; *p != NULL; )
		{
			if ( ( val = DASet_Hash( ( *p )->s ) & mask ) != i )
			{
				key = *p;
				*p = ( *p )->next;
				key->next = h->tbl[val];
				h->tbl[val] = key;
			}
			else
				p = &( *p )->next;
		}
	}
}

// Expand a hash table.
static	int		DASet_Expand( hDASet h )
{
	int		i, max, nbit;
	hDAKey	*tbl;

	// Calculate the size of hash table and allocate memory.
	nbit = ( h->nbit < HASH_MIN ) ? HASH_MIN : ( h->nbit + 1 );
	tbl = ( hDAKey * )realloc( h->tbl, sizeof( *tbl ) << nbit );
	if ( tbl == NULL )
		return	DA_EMEM;
	h->tbl = tbl;

	// Move keys to the new position and clear new area.
	if ( h->nbit < HASH_MIN )
	{
		for ( i = 0, max = 1 << nbit; i < max; i++ )
			tbl[i] = NULL;
	}
	else
		DASet_Divide( h, nbit );

	h->nbit = nbit;
	h->mask = ( 1 << nbit ) - 1;

	return	DA_OK;
}

// Search a key from a hash table.
static	hDAKey	*DASet_Search( hDASet h, const char *key )
{
	int		val;
	hDAKey	*p;

	val = DASet_Hash( key ) & h->mask;
	for ( p = &h->tbl[val]; *p != NULL; p = &( *p )->next )
	{
		if ( !DAStr_Cmp( ( *p )->s, key ) )
			break;
	}

	return	p;
}

// Insert a key to a hash table.
static	int		DASet_Add( hDASet h, const char *key, int rec )
{
	int		ret;
	hDAKey	*p;

	// Expand a hash table if required.
	if ( h->n >= 1 << h->nbit )
	{
		if ( ( ret = DASet_Expand( h ) ) != DA_OK )
			return	ret;
	}

	if ( *( p = DASet_Search( h, key ) ) == NULL )
	{
		// Add a new key if it is not registered.
		if ( ( *p = DAKey_Create( key ) ) == NULL )
			return	DA_EMEM;
		h->n++;
	}

	// Overwrite the record size.
	( *p )->rec = rec;

	return	DA_OK;
}


// Text file which includes keys.


// Initialize a structure.
static	void	DAFile_Init( hDAFile h, int size )
{
	memset( h, 0, sizeof( *h ) );

	h->size = size;
}

// Create structure.
static	hDAFile		DAFile_Create( int size )
{
	hDAFile		h;

	if ( ( h = ( hDAFile )malloc( sizeof( *h ) + size + 1 ) ) != NULL )
		DAFile_Init( h, size );

	return	h;
}

// Clear structure.
static	void	DAFile_Finish( hDAFile h )
{
}

// Destroy structure.
static	void	DAFile_Delete( hDAFile h )
{
	DAFile_Finish( h );
	free( h );
}

// Loads the whole file to memory.
static	int		DAFile_Load( hDAFile h, FILE *fp )
{
	if ( fread( h->buf, h->size, 1, fp ) != 1 )
		return	DA_EIO;
	h->buf[ h->size ] = '\0';

	return	DA_OK;
}

// Allocate memory to store the whole file.
static	int		DAFile_Alloc( hDAFile *h, FILE *fp )
{
	int		size;

	if ( fseek( fp, 0, SEEK_END ) == -1 ||
		 ( size = ftell( fp ) ) == -1 ||
		 fseek( fp, 0, SEEK_SET ) == -1 )
		return	DA_EIO;

	if ( ( *h = DAFile_Create( size ) ) == NULL )
		return	DA_EMEM;

	return	DA_OK;
}

// Open a file and read its contents.
static	int		DAFile_Open( hDAFile *h, const char *path )
{
	int		ret;
	FILE	*fp;

	if ( ( fp = fopen( path, "rb" ) ) == NULL )
		return	DA_EIO;

	if ( ( ret = DAFile_Alloc( h, fp ) ) == DA_OK )
	{
		if ( ( ret = DAFile_Load( *h, fp ) ) != DA_OK )
			DAFile_Delete( *h );
	}

	fclose( fp );

	return	ret;
}

// Destroy contents of a file.
static	void	DAFile_Close( hDAFile h )
{
	DAFile_Delete( h );
}

// Check if a character is a delimitor or not.
static	int		DAFile_IsDelim( const char *delim, char c )
{
	while ( *delim != '\0' )
	{
		if ( c == *delim++ )
			return	1;
	}

	return	c == '\0';
}

// Cut out a key from a text by using delimitors.
static	const char	*DAFile_Delim( hDAFile h, const char *delim )
{
	const char	*start;

	// Get the beginning of a key.
	while ( h->pos < h->size && DAFile_IsDelim( delim, h->buf[ h->pos ] ) )
		h->pos++;
	if ( h->pos >= h->size )
		return	NULL;
	start = h->buf + h->pos;

	// Get the end of a key.
	while ( !DAFile_IsDelim( delim, h->buf[ h->pos ] ) )
		h->pos++;
	h->buf[ h->pos++ ] = '\0';

	return	start;
}


// Input keys from a file.


// Add keys in a file to a keyset.
static	int		DASet_FileAdd( hDASet h, hDAFile file,
							   const char *delim, int rec )
{
	int		ret;
	const char	*key;

	while ( ( key = DAFile_Delim( file, delim ) ) != NULL )
	{
		if ( ( ret = DASet_Insert( h, key, rec ) ) != DA_OK )
			return	ret;
	}

	return	DA_OK;
}


// Sorting of a keyset.


// Initialize a structure.
static	void	DASort_Init( hDASort h, int n )
{
	memset( h, 0, sizeof( *h ) );

	h->n = n;
}

// Create a structure.
static	hDASort		DASort_Create( int n )
{
	int		size;
	hDASort		h;

	size = sizeof( *h ) + sizeof( *h->key ) * n;
	if ( ( h = ( hDASort )malloc( size ) ) != NULL )
		DASort_Init( h, n );

	return	h;
}

// Clear a structure.
static	void	DASort_Finish( hDASort h )
{
}

// Destroy a structure.
static	void	DASort_Delete( hDASort h )
{
	DASort_Finish( h );
	free( h );
}

// Multi-key quick sort.
static	void	DASort_Quick( hDAKey *key, int n, int depth );

// Swap 2 keys.
static	void	DASort_Swap( hDAKey *key, int x, int y )
{
	hDAKey	tmp;

	tmp = key[x];
	key[x] = key[y];
	key[y] = tmp;
}

// Choose a pivot.
static	void	DASort_Pivot( hDAKey *key, int n, int depth )
{
	// If the first key is less than the center key.
	if ( ( unsigned char )key[0]->s[depth] <
		 ( unsigned char )key[ n >> 1 ]->s[depth] )
		DASort_Swap( key, 0, n >> 1 );

	// If the last key is less than the middle key.
	if ( ( unsigned char )key[ n - 1 ]->s[depth] <
		 ( unsigned char )key[ n >> 1 ]->s[depth] )
	{
		DASort_Swap( key, 0, n >> 1 );
		DASort_Swap( key, n >> 1, n - 1 );
	}
	// If the last key is less than the first key.
	else if ( ( unsigned char )key[ n - 1 ]->s[depth] <
			  ( unsigned char )key[0]->s[depth] )
		DASort_Swap( key, 0, n - 1 );

	// Swap the 2nd key and the middle key.
	DASort_Swap( key, 1, n >> 1 );
}

// Insert sort.
static	void	DASort_Insert( hDAKey *key, int n, int depth )
{
	int		i, j;
	const char	*s;

	for ( i = 1; i < n; i++ )
	{
		s = key[i]->s + depth;
		for ( j = i; j > 0; j-- )
		{
			if ( DAStr_Cmp( s, key[ j - 1 ]->s + depth ) > 0 )
				break;
			DASort_Swap( key, j - 1, j );
		}
	}
}

// Subroutine of multi-key sort.
static	void	DASort_QuickSub( hDAKey *key, int n, int depth,
								 int l, unsigned char pivot )
{
	int		i, r, pl, pr, mv, diff;

	pl = l;
	pr = r = n - 1;

	// Partitioning.
	for ( ; ; )
	{
		// Move pivots to left.
		while ( l <= r )
		{
			if ( ( diff = ( unsigned char )key[l]->s[depth] - pivot ) > 0 )
				break;
			else if ( !diff )
				DASort_Swap( key, l, pl++ );
			l++;
		}
		// Move pivots to right.
		while ( l <= r )
		{
			if ( ( diff = ( unsigned char )key[r]->s[depth] - pivot ) < 0 )
				break;
			else if ( !diff )
				DASort_Swap( key, r, pr-- );
			r--;
		}

		if ( l > r )
			break;

		DASort_Swap( key, l++, r-- );
	}

	// Move left-side pivots to middle.
	mv = ( pl < l - pl ) ? pl : l - pl;
	for ( i = 0; i < mv; i++ )
		DASort_Swap( key, i, r - i );
	pl = l - pl;

	// Move right-side pivots to middle.
	n--;
	mv = ( n - pr < pr - r ) ? n - pr : pr - r;
	for ( i = 0; i < mv; i++ )
		DASort_Swap( key, l + i, n - i );
	pr = ++n - ( pr - r );

	// Sort keys recursively.
	if ( pl > 1 )
		DASort_Quick( key, pl, depth );
	if ( pr - pl > 1 )
		DASort_Quick( key + pl, pr - pl, depth + 1 );
	if ( n - pr > 1 )
		DASort_Quick( key + pr, n - pr, depth );
}

// Multi-key quick sort.
static	void	DASort_Quick( hDAKey *key, int n, int depth )
{
	int		i;
	unsigned char	pivot;

	if ( n < 8 )
	{
		// Use insert sort for a small keyset.
		DASort_Insert( key, n, depth );
		return;
	}

	depth--;
	do
	{
		// If all keys are equal to a pivot, skip one loop.
		DASort_Pivot( key, n, ++depth );
		pivot = ( unsigned char )key[0]->s[depth];

		for ( i = 1; i < n; i++ )
		{
			if ( ( unsigned char )key[i]->s[depth] != pivot )
				break;
		}
	}	while ( i == n );

	DASort_QuickSub( key, n, depth, i, pivot );
}

// Bucket sort.
static	void	DASort_Bin( hDAKey *key, hDASet set )
{
	int		i, max, depth;
	int		buf[258], *freq;
	hDAKey	p;

	depth = 0;
	max = 1 << set->nbit;

	do
	{
		// Count frequencies.
		freq = buf + 2;
		memset( buf, 0, sizeof( buf ) );
		for ( i = 0; i < max; i++ )
		{
			for ( p = set->tbl[i]; p != NULL; p = p->next )
				freq[ ( unsigned char )p->s[depth] ]++;
		}

		// Calculate total frequencies.
		for ( i = 1, freq--; i < 256; i++ )
		{
			if ( freq[i] == set->n && set->n > 1 )
			{
				depth++;
				break;
			}
			freq[i] += freq[ i - 1 ];
		}
	}	while ( i < 256 );

	// Divide keys by letters with the depth.
	for ( i = 0; i < max; i++ )
	{
		for ( p = set->tbl[i]; p != NULL; p = p->next )
			key[ freq[ ( unsigned char )p->s[depth] ]++ ] = p;
	}

	// Sort keys by deeper letters.
	for ( i = 0, freq--, depth++; i < 256; i++ )
	{
		if ( freq[ i + 1 ] - freq[i] > 1 )
			DASort_Quick( key + freq[i], freq[ i + 1 ] - freq[i], depth );
	}
}

// Confirm record size and key length.
static	void	DASort_Check( hDASort h )
{
	int		i;

	if ( h->n )
	{
		h->max = h->key[0]->rec;
		h->depth = h->key[0]->len;
	}

	for ( i = 1; i < h->n; i++ )
	{
		// Maximum record size, kinds of record size and maximum key length.
		if ( h->key[i]->rec > h->max )
			h->max = h->key[i]->rec;
		if ( h->key[ i - 1 ]->rec != h->key[i]->rec )
			h->type = 1;
		if ( h->key[i]->len > h->depth )
			h->depth = h->key[i]->len;
	}
}


// Middle interface.


// Generate sorted keyset.
static	int		DASort_Open( hDASort *h, hDASet set )
{
	// Allocate memory.
	if ( ( *h = DASort_Create( set->n ) ) == NULL )
		return	DA_EMEM;

	// Multi-key quick sort after bin sort.
	DASort_Bin( ( *h )->key, set );

	// Check record information.
	DASort_Check( *h );

	return	DA_OK;
}

// Destroy sorted keyset.
static	void	DASort_Close( hDASort h )
{
	DASort_Delete( h );
}


// Sort suffixes in descending order.


// Multi-key quick sort.
static	void	DASuffix_Quick( hDAKey *key, int n, int depth );

// Get a latter of suffix.
static	int		DASuffix_Char( hDAKey key, int depth )
{
	if ( depth >= key->len - key->depth )
		return	'\0';

	return	( unsigned char )key->s[ key->len - depth - 1 ];
}

// Compare 2 suffixes.
static	int		DASuffix_Cmp( hDAKey a, hDAKey b, int depth )
{
	int		ac, bc;

	do
	{
		ac = DASuffix_Char( a, depth );
		bc = DASuffix_Char( b, depth++ );
	}	while ( ac != '\0' && ac == bc );

	return	ac - bc;
}

// Check if a suffix is unified by another suffix.
static	int		DASuffix_Part( hDAKey prev, hDAKey key )
{
	int		ac, bc, depth = 0;

	do
	{
		ac = DASuffix_Char( prev, depth );
		bc = DASuffix_Char( key, depth++ );
	}	while ( ac != '\0' && ac == bc );

	return	bc == '\0';
}

// Unify same suffixes.
static	void	DASuffix_Unify( hDAKey *key, int n )
{
	int		i;

	for ( i = 0; i < n; i++ )
		key[i]->unify = 1;
}

// Choose a pivot.
static	void	DASuffix_Pivot( hDAKey *key, int n, int depth )
{
	// If the first suffix is greater than the middle suffix.
	if ( DASuffix_Char( key[0], depth ) >
		 DASuffix_Char( key[ n >> 1 ], depth ) )
		DASort_Swap( key, 0, n >> 1 );

	// If the last suffix is greater than the middle suffix.
	if ( DASuffix_Char( key[ n - 1 ], depth ) >
		 DASuffix_Char( key[ n >> 1 ], depth ) )
	{
		DASort_Swap( key, 0, n >> 1 );
		DASort_Swap( key, n >> 1, n - 1 );
	}
	// If the last suffix is greater than the first suffix.
	else if ( DASuffix_Char( key[ n - 1 ], depth ) >
			  DASuffix_Char( key[0], depth ) )
		DASort_Swap( key, 0, n - 1 );

	// Swap the second suffix and the middle suffix.
	DASort_Swap( key, 1, n >> 1 );
}

// Insert sort.
static	void	DASuffix_Insert( hDAKey *key, int n, int depth )
{
	int		i, j;

	for ( i = 1; i < n; i++ )
	{
		for ( j = i; j > 0; j-- )
		{
			if ( DASuffix_Cmp( key[j], key[ j - 1 ], depth ) < 0 )
				break;
			DASort_Swap( key, j - 1, j );
		}
	}
}

// Subroutine of multi-key quick sort.
static	void	DASuffix_QuickSub( hDAKey *key, int n, int depth,
								   int l, int pivot )
{
	int		i, r, pl, pr, mv, diff;

	pl = l;
	pr = r = n - 1;

	// Partitioning.
	for ( ; ; )
	{
		// Move pivots to left.
		while ( l <= r )
		{
			if ( ( diff = DASuffix_Char( key[l], depth ) - pivot ) < 0 )
				break;
			else if ( !diff )
				DASort_Swap( key, l, pl++ );
			l++;
		}
		// Move pivots to right.
		while ( l <= r )
		{
			if ( ( diff = DASuffix_Char( key[r], depth ) - pivot ) > 0 )
				break;
			else if ( !diff )
				DASort_Swap( key, r, pr-- );
			r--;
		}

		if ( l > r )
			break;

		DASort_Swap( key, l++, r-- );
	}

	// Move left pivots to center.
	mv = ( pl < l - pl ) ? pl : l - pl;
	for ( i = 0; i < mv; i++ )
		DASort_Swap( key, i, r - i );
	pl = l - pl;
	// Move right pivots to center.
	n--;
	mv = ( n - pr < pr - r ) ? n - pr : pr - r;
	for ( i = 0; i < mv; i++ )
		DASort_Swap( key, l + i, n - i );
	pr = ++n - ( pr - r );

	// Sort suffixes recursively.
	if ( pl > 1 )
		DASuffix_Quick( key, pl, depth );
	if ( pr - pl > 1 )
	{
		if ( pivot != '\0' )
			DASuffix_Quick( key + pl, pr - pl, depth + 1 );
		else
			DASuffix_Unify( key + pl, pr - pl );
	}
	if ( n - pr > 1 )
		DASuffix_Quick( key + pr, n - pr, depth );
}

// Multi-key quick sort.
static	void	DASuffix_Quick( hDAKey *key, int n, int depth )
{
	int		i, pivot;

	if ( n < 8 )
	{
		// Use insert sort for a small keyset.
		DASuffix_Insert( key, n, depth );
		return;
	}

	depth--;
	do
	{
		// If all keys are equal to a pivot, skip one loop.
		DASuffix_Pivot( key, n, ++depth );
		pivot = DASuffix_Char( key[0], depth );

		for ( i = 1; i < n; i++ )
		{
			if ( DASuffix_Char( key[i], depth ) != pivot )
				break;
		}
	}	while ( i == n && pivot != '\0' );

	if ( i < n )
		DASuffix_QuickSub( key, n, depth, i, pivot );
	else
		DASuffix_Unify( key + 1, n - 1 );
}

// Check suffixes which are to be unified.
static	void	DASuffix_Check( hDASort h )
{
	int		i;

	for ( i = 1; i < h->n; i++ )
	{
		// Check if the previous key is unified or not.
		if ( !h->key[i]->unify )
			h->key[i]->unify = DASuffix_Part( h->key[ i - 1 ], h->key[i] );
	}
}

// Sort suffixes in descending order.
static	void	DASuffix_Sort( hDASort h )
{
	// Multi-key quick sort and unify suffixes.
	DASuffix_Quick( h->key, h->n, 0 );
	DASuffix_Check( h );
}


// External interfaces.


// Creates an empty keyset.
int		DASet_Open( hDASet *h )
{
	int		ret;

	if ( h == NULL )
		return	DA_EHDL;

	// Create a structure.
	if ( ( *h = DASet_Create() ) == NULL )
		return	DA_EMEM;

	// Initialize a hash table.
	if ( ( ret = DASet_Expand( *h ) ) != DA_OK )
	{
		DASet_Delete( *h );
		*h = NULL;
	}

	return	ret;
}

// Load a keyset from a text file.
// Delimitors of keys are specified by the 3rd argument.
// For example, if "\t\r\n" has passed as the 3rd argument, tabs, carriage
// returns and line feeds are used as delimitors.
// The 4th argument specifies the size of each record.
int		DASet_Load( hDASet h, const char *path, const char *delim, int rec )
{
	int		ret;
	hDAFile		file;

	if ( h == NULL )
		return	DA_EHDL;
	else if ( path == NULL || delim == NULL )
		return	DA_EARG;

	// Load keys and add them to a keyset.
	if ( ( ret = DAFile_Open( &file, path ) ) != DA_OK )
		return	ret;

	ret = DASet_FileAdd( h, file, delim, rec );

	DAFile_Close( file );

	return	DA_OK;
}

// Insert a key to a keyset.
// The 3rd argument specifies the size of each record.
int		DASet_Insert( hDASet h, const char *key, int rec )
{
	if ( h == NULL )
		return	DA_EHDL;
	else if ( key == NULL )
		return	DA_EARG;

	// Adjust a record size.
	if ( rec < 0 )
		rec = 0;

	return	DASet_Add( h, key, rec );
}

// Destroy a keyset.
int		DASet_Close( hDASet h )
{
	if ( h == NULL )
		return	DA_EHDL;

	DASet_Delete( h );

	return	DA_OK;
}


//
// Dictionary.
//


// Macros.


// Version information.
#define		DA_VERSION	123		// Current version.
#define		DA_COMPAT	120		// Compatible version.

// Letters which identify a header of file.
#define		HEAD_STR	"TDA"

// Temporary information to construct a dictionary.
// Empty elements have FLAG_USED, and if a BASE is used,
// corresponding elements have FLAG_BASE.
#define		FLAG_USED	( 1 << 0 )
#define		FLAG_BASE	( 1 << 1 )

// Upper limit of size.
#define		BC_MAX		( VAL_BASE + 1 )	// 8,388,608
#define		TAIL_MAX	VAL_LINK			// 2,147,483,647

// Index of the root.
#define		IDX_ROOT	0

// Contents of BC.
#define		VAL_LEAF	0x00000001U
#define		VAL_BASE	0x007FFFFFU
#define		VAL_CHECK	0x000000FFU
#define		VAL_LINK	0x7FFFFFFFU
#define		OFF_LEAF	31
#define		OFF_BASE	8
#define		OFF_CHECK	0
#define		OFF_LINK	0
#define		MASK_LEAF	( VAL_LEAF << OFF_LEAF )
#define		MASK_BASE	( VAL_BASE << OFF_BASE )
#define		MASK_CHECK	( VAL_CHECK << OFF_CHECK )
#define		MASK_LINK	( VAL_LINK << OFF_LINK )

// Byte bordary.
#define		BOUND_MIN	( 1 << 0 )	//	1 byte.
#define		BOUND_MAX	( 1 << 16 )	//	65,536 bytes.


//
// Structures.
//


// Element of BC.
typedef		unsigned	DAInt, *hDAInt;

// Structure to enumerate keys.
typedef		struct DAEnum
{
	int		*idx;	// Index.
	char	*key;	// Key.
}	DAEnum, *hDAEnum;

// Arc.
typedef		struct DAArc
{
	int		c;	// Arc label.
	int		n;	// Frequency of an arc label.
}	DAArc, *hDAArc;

// Siblings.
typedef		struct DASib
{
	DAArc	arc[256];	// Arcs.
	int		n;			// Number of valid arcs.
}	DASib, *hDASib;

// Temporary information to construct a dictionary.
typedef		struct DAInf
{
	hDADic		dic;	// Dictionary.
	hDASort		sort;	// Sorted keyset.
	hDASib		sib;	// Siblings.
	char		*flag;	// Flags.
	int			n;		// Size of flags buffer.
	int			ntail;	// Length of TAIL.
	int			max;	// The last used element.
	int			empty;	// The first empty element.
	int			pos;	// Position to insert the next suffix.
	int			mask;	// Mask for byte boundary.
}	DAInf, *hDAInf;

// Header of dictionary file.
typedef		struct DAHead
{
	char	str[4];		// Letters to identify the dictionary file.
	int		version;	// Version.
	int		nbc;		// Length of BC.
	int		ntail;		// Length of TAIL.
	int		nkey;		// Number of keys.
	int		maxlen;		// Maximum key length.
	int		nbit;		// Lower bits to unify suffixes.
	int		boundary;	// Byte boundary.
	int		rec;		// Condition of records.
	int		space[7];	// Reserved.
}	DAHead, *hDAHead;

// Dictionary.
typedef		struct DADic
{
	hDAInt	bc;			// Array BC (BASE and CHECK).
	char	*tail;		// Array TAIL.
	int		nbc;		// Length of BC.
	int		ntail;		// Length of TAIL.
	int		nkey;		// Number of keys.
	int		maxlen;		// Maximum key length.
	int		nbit;		// Lower bits to unify suffixes.
	DAInt	hmask;		// Upper mask.
	DAInt	lmask;		// Lower mask.
	int		boundary;	// Byte boundary.
	int		rec;		// Condition of records.
}	DADic;


// Handling of elements.


// Read LEAF.
static	int		DAInt_Leaf( hDAInt h )
{
	return	( int )( ( *h & MASK_LEAF ) >> OFF_LEAF );
}

// Write LEAF.
static	void	DAInt_WLeaf( hDAInt h, int val )
{
	*h &= ~MASK_LEAF;
	*h |= ( ( DAInt )val & VAL_LEAF ) << OFF_LEAF;
}

// Read BASE.
static	int		DAInt_Base( hDAInt h )
{
	return	( int )( ( *h & MASK_BASE ) >> OFF_BASE );
}

// Write BASE.
static	void	DAInt_WBase( hDAInt h, int val )
{
	*h &= ~MASK_BASE;
	*h |= ( ( DAInt )val & VAL_BASE ) << OFF_BASE;
}

// Read CHECK.
static	int		DAInt_Check( hDAInt h )
{
	return	( int )( ( *h & MASK_CHECK ) >> OFF_CHECK );
}

// Write CHECK.
static	void	DAInt_WCheck( hDAInt h, int val )
{
	*h &= ~MASK_CHECK;
	*h |= ( ( DAInt )val & VAL_CHECK ) << OFF_CHECK;
}


// Creation and destruction of a dictionary.


// Initialize a dictionary.
static	void	DADic_Init( hDADic h )
{
	memset( h, 0, sizeof( *h ) );

	h->bc = NULL;
	h->tail = NULL;
}

// Create a dictionary.
static	hDADic	DADic_Create( void )
{
	hDADic	h;

	if ( ( h = ( hDADic )malloc( sizeof( *h ) ) ) != NULL )
		DADic_Init( h );

	return	h;
}

// Clear a dictionary.
static	void	DADic_Finish( hDADic h )
{
	if ( h->bc != NULL )
		free( h->bc );
	if ( h->tail != NULL )
		free( h->tail );
}

// Destroy a dictionary.
static	void	DADic_Delete( hDADic h )
{
	DADic_Finish( h );
	free( h );
}

// Resize BC.
static	int		DADic_ResizeBC( hDADic h, int n )
{
	hDAInt	bc;

	// Reallocate memory.
	if ( ( bc = ( hDAInt )realloc( h->bc, sizeof( *bc ) * n ) ) == NULL )
		return	DA_EMEM;

	h->bc = bc;
	h->nbc = n;

	return	DA_OK;
}

// Resize TAIL.
static	int		DADic_ResizeTail( hDADic h, int n )
{
	char	*tail;

	// Reallocate memory.
	if ( ( tail = ( char * )realloc( h->tail, n ) ) == NULL )
		return	DA_EMEM;

	h->tail = tail;
	h->ntail = n;

	return	DA_OK;
}


// Handling of a dictionary.


// Read LEAF.
static	int		DADic_Leaf( hDADic h, int idx )
{
	return	DAInt_Leaf( h->bc + idx );
}

// Write LEAF.
static	void	DADic_WLeaf( hDADic h, int idx, int val )
{
	DAInt_WLeaf( h->bc + idx, val );
}

// Read BASE.
static	int		DADic_Base( hDADic h, int idx )
{
	return	DAInt_Base( h->bc + idx );
}

// Write BASE.
static	void	DADic_WBase( hDADic h, int idx, int val )
{
	DAInt_WBase( h->bc + idx, val );
}

// Read CHECK.
static	int		DADic_Check( hDADic h, int idx )
{
	return	DAInt_Check( h->bc + idx );
}

// Write CHECK.
static	void	DADic_WCheck( hDADic h, int idx, int val )
{
	DAInt_WCheck( h->bc + idx, val );
}

// Read POS.
static	int		DADic_Pos( hDADic h, int idx )
{
	return	( int )( h->bc[idx] & h->hmask ) >> h->nbit;
}

// Write POS.
static	void	DADic_WPos( hDADic h, int idx, int val )
{
	h->bc[idx] &= ~h->hmask;
	h->bc[idx] |= ( ( DAInt )val << h->nbit ) & h->hmask;
}

// Read REC.
static	int		DADic_Rec( hDADic h, int idx )
{
	return	( int )( h->bc[idx] & h->lmask );
}

// Write REC.
static	void	DADic_WRec( hDADic h, int idx, int val )
{
	h->bc[idx] &= ~h->lmask;
	h->bc[idx] |= ( DAInt )val & h->lmask;
}

// Read TAIL.
static	char	*DADic_Str( hDADic h, int pos )
{
	return	h->tail + pos;
}

// Write TAIL.
static	void	DADic_WStr( hDADic h, int pos, const char *s )
{
	DAStr_Copy( h->tail + pos, s );
}

// Generate a mask.
static	void	DADic_SetMask( hDADic h, int nbit )
{
	h->nbit = nbit;
	h->lmask = ( ( DAInt )1 << nbit ) - 1;
	h->hmask = MASK_LINK & ~h->lmask;
}


// Creation and destruction of temporary information.


// Initialize.
static	void	DAInf_Init( hDAInf h, hDADic dic, hDASort sort )
{
	memset( h, 0, sizeof( *h ) );

	h->dic = dic;
	h->sort = sort;
	h->sib = NULL;
	h->flag = NULL;
}

// Create.
static	hDAInf	DAInf_Create( hDADic dic, hDASort sort )
{
	hDAInf	h;

	if ( ( h = ( hDAInf )malloc( sizeof( *h ) ) ) != NULL )
		DAInf_Init( h, dic, sort );

	return	h;
}

// Clear.
static	void	DAInf_Finish( hDAInf h )
{
	if ( h->flag != NULL )
		free( h->flag );
	if ( h->sib != NULL )
		free( h->sib );
}

// Destroy.
static	void	DAInf_Delete( hDAInf h )
{
	DAInf_Finish( h );
	free( h );
}


// Get siblings.


// Get siblings.
static	void	DASib_Scan( hDASib h, hDAKey *key, int n, int depth )
{
	int		i, type;

	// First arc.
	h->arc[0].c = ( unsigned char )key[0]->s[depth];
	h->arc[0].n = 1;

	// Count each arc label.
	for ( i = 1, type = 0; i < n; i++ )
	{
		if ( h->arc[type].c == ( unsigned char )key[i]->s[depth] )
			h->arc[type].n++;
		else
		{
			h->arc[ ++type ].c = ( unsigned char )key[i]->s[depth];
			h->arc[type].n = 1;
		}
	}

	h->n = type + 1;
}


// Handling of construction space.


// Allocate memory to siblings.
static	int		DAInf_ResizeSib( hDAInf h, int n )
{
	hDASib	sib;

	if ( ( sib = ( hDASib )realloc( h->sib, sizeof( *sib ) * n ) ) == NULL )
		return	DA_EMEM;
	h->sib = sib;

	return	DA_OK;
}

// Allocate memory to siblings.
static	int		DAInf_ExpandSib( hDAInf h )
{
	return	DAInf_ResizeSib( h, h->sort->depth );
}

// Initialize expanded space.
static	void	DAInf_ClearBC( hDAInf h, int n )
{
	int		i;
	hDAInt	bc = h->dic->bc;

	if ( n > h->n )
	{
		// Clear flags and connect empty elements.
		memset( h->flag + h->n, 0, n - h->n );
		for ( i = h->n; i < n; i++ )
			bc[i] = i + 1;
	}

	h->n = n;
}

// Resize BC.
static	int		DAInf_ResizeBC( hDAInf h, int n )
{
	int		ret;
	char	*flag;

	// Reallocate memory.
	if ( ( flag = ( char * )realloc( h->flag, n ) ) == NULL )
		return	DA_EMEM;
	h->flag = flag;

	// Resize BC and initialize expanded elements.
	if ( ( ret = DADic_ResizeBC( h->dic, n ) ) != DA_OK )
		return	ret;
	DAInf_ClearBC( h, n );

	return	DA_OK;
}

// Expand BC.
static	int		DAInf_ExpandBC( hDAInf h )
{
	int		size;

	// Upper limit of size.
	if ( h->n >= BC_MAX )
		return	DA_EMAX;

	size = h->n ? h->n : h->sort->n;
	size = ( ( size + ( size >> 1 ) ) + 0x100 ) & ~0xFF;
	if ( size > BC_MAX )
		size = BC_MAX;

	return	DAInf_ResizeBC( h, size );
}

// Reduce the size of BC.
static	int		DAInf_ReduceBC( hDAInf h )
{
	int		size;

	size = ( h->max + 0x100 ) & ~0xFF;

	return	DAInf_ResizeBC( h, size );
}

// Initialize new space of TAIL.
static	void	DAInf_ClearTail( hDAInf h, int n )
{
	if ( n > h->ntail )
		memset( h->dic->tail + h->ntail, 0, n - h->ntail );

	h->ntail = n;
}

// Resize TAIL.
static	int		DAInf_ResizeTail( hDAInf h, int n )
{
	int		ret;

	// Reallocate memory and initialize new space.
	if ( ( ret = DADic_ResizeTail( h->dic, n ) ) != DA_OK )
		return	ret;
	DAInf_ClearTail( h, n );

	return	DA_OK;
}

// Reduce TAIL.
static	int		DAInf_ReduceTail( hDAInf h )
{
	if ( h->pos == h->ntail )
		return	DA_OK;

	return	DADic_ResizeTail( h->dic, h->pos );
}


// Subroutines for construction.


// Check if an element is used or not.
static	int		DAInf_Used( hDAInf h, int idx )
{
	return	h->flag[idx] & FLAG_USED;
}

// Check if a BASE is used or not.
static	int		DAInf_Base( hDAInf h, int idx )
{
	return	( h->flag[idx] & FLAG_BASE ) == FLAG_BASE;
}

// Next empty element.
static	int		DAInf_NextEmpty( hDAInf h, int idx )
{
	int		next;

	// Candidate of the next empty element.
	next = h->dic->bc[idx];

	// Find an empty element.
	while ( next < h->n && DAInf_Used( h, next ) )
		next++;

	// Modify the candidate of the next empty element.
	h->dic->bc[idx] = next;

	return	next;
}

// Set a flag which indiates an element is used or not.
static	void	DAInf_WUsed( hDAInf h, int idx )
{
	// Modify the first empty element.
	if ( idx == h->empty )
		h->empty = DAInf_NextEmpty( h, idx );

	// Modify the last used element.
	if ( idx > h->max )
		h->max = idx;

	h->flag[idx] |= FLAG_USED;
}

// Set a flag which indicates a BASE is used or not.
static	void	DAInf_WBase( hDAInf h, int idx )
{
	h->flag[idx] |= FLAG_BASE;
}

// Create the root.
static	int		DAInf_Root( hDAInf h )
{
	int		ret;

	// Allocate memory to BC.
	// According to experiences the number of elements will be 1.5 times of
	// the number of keys.
	if ( ( ret = DAInf_ExpandBC( h ) ) != DA_OK )
		return	ret;

	DAInf_WUsed( h, IDX_ROOT );
	DAInf_WBase( h, IDX_ROOT );
	DADic_WLeaf( h->dic, IDX_ROOT, 0 );
	DADic_WBase( h->dic, IDX_ROOT, IDX_ROOT );
	DADic_WCheck( h->dic, IDX_ROOT, '\0' );

	return	DA_OK;
}


// Construction of BC.


// Find a good BASE.
static	int		DAInf_Search( hDAInf h, hDASib sib )
{
	int		i, empty, base;

	// Find empty elements.
	for ( empty = h->empty; empty < h->n; empty = DAInf_NextEmpty( h, empty ) )
	{
		// Check the BASE is used or not.
		base = empty ^ sib->arc[0].c;
		if ( DAInf_Base( h, base ) )
			continue;

		// Check if siblings are stored correctly.
		for ( i = 1; i < sib->n; i++ )
		{
			if ( DAInf_Used( h, base ^ sib->arc[i].c ) )
				break;
		}
		if ( i == sib->n )
			return	base;
	}

	return	empty ^ sib->arc[0].c;
}

// Arrange siblings.
static	int		DAInf_Arrange( hDAInf h, hDASib sib, int idx )
{
	int		i, base, next, ret;

	// Arrange siblings and expand BC if required.
	if ( ( base = DAInf_Search( h, sib ) ) >= h->n )
	{
		if ( ( ret = DAInf_ExpandBC( h ) ) != DA_OK )
			return	ret;
	}

	// Set BASE and CHECK.
	DAInf_WBase( h, base );
	DADic_WBase( h->dic, idx, base );

	for ( i = 0; i < sib->n; i++ )
	{
		next = base ^ sib->arc[i].c;
		DAInf_WUsed( h, next );
		DADic_WCheck( h->dic, next, sib->arc[i].c );
	}

	return	DA_OK;
}

// Depth-first construction.
static	int		DAInf_Progress( hDAInf h, hDAKey *key, int n,
								int idx, int depth )
{
	int		i, single, base, ret;
	hDASib	sib;

	// Leaf node.
	single = depth && ( n == 1 );
	DADic_WLeaf( h->dic, idx, single );
	if ( single )
	{
		key[0]->idx = idx;
		key[0]->depth = depth - 1;
		return DA_OK;
	}

	// Get siblings and arrange them.
	sib = h->sib + depth;
	DASib_Scan( sib, key, n, depth );
	if ( ( ret = DAInf_Arrange( h, sib, idx ) ) != DA_OK )
		return	ret;
	base = DADic_Base( h->dic, idx );

	// Recursive construction.
	for ( i = 0; i < sib->n; i++ )
	{
		ret = DAInf_Progress( h, key, sib->arc[i].n,
							  base ^ sib->arc[i].c, depth + 1 );
		if ( ret != DA_OK )
			return	ret;

		key += sib->arc[i].n;
	}

	return	DA_OK;
}

// Build BC.
static	int		DAInf_BuildBC( hDAInf h )
{
	int		ret;

	// Empty dictionary.
	if ( h->sort->n <= 0 )
	{
		DAInf_WBase( h, IDX_ROOT ^ 1 );
		DADic_WBase( h->dic, IDX_ROOT, IDX_ROOT ^ 1 );
		return	DA_OK;
	}

	// Allocate memory to siblings.
	if ( ( ret = DAInf_ExpandSib( h ) ) != DA_OK )
		return	ret;

	// Depth-first construction.
	ret = DAInf_Progress( h, h->sort->key, h->sort->n, IDX_ROOT, 0 );
	if ( ret != DA_OK )
		return	ret;

	return	DA_OK;
}

// Revise empty elements.
static	void	DAInf_Revise( hDAInf h )
{
	int		empty, next, base = 0, block = -1;

	for ( empty = h->empty; empty < h->n; empty = next )
	{
		next = DAInf_NextEmpty( h, empty );

		// Find an unused empty element in the block.
		if ( empty >> 8 != block )
		{
			block = empty >> 8;
			base = block << 8;
			while ( DAInf_Base( h, base ) )
				base++;
		}

		// Set an empty element.
		DADic_WLeaf( h->dic, empty, 0 );
		DADic_WBase( h->dic, empty, 0 );
		DADic_WCheck( h->dic, empty, ( base ^ empty ) & 0xFF );
	}
}


// Construction of TAIL.


// Confirm if an unification is required or not.
static	int		DAInf_NeedUnify( hDAInf h )
{
	if ( h->sort->max <= h->dic->boundary )
		return	1;

	return	!h->sort->type;
}

// Judge if byte boundary should be applied or not.
static	int		DAInf_NeedBoundary( hDAInf h, int no )
{
	int		max;
	hDAKey	*key;

	max = h->sort->max;
	key = h->sort->key;
	do
	{
		// Need records.
		if ( key[no]->rec )
			return	1;
	}	while ( ++no < max && key[no]->unify );

	// No need.
	return	0;
}

// Calculate the record period.
static	void	DAInf_RecordPeriod( hDAInf h )
{
	h->mask = h->dic->boundary - 1;

	if ( DAInf_NeedUnify( h ) )
		h->dic->rec = ( h->sort->max + h->mask ) & ~h->mask;

}

// Calculate the required size and allocate memory to TAIL.
static	int		DAInf_TotalTail( hDAInf h )
{
	int		i, max, len, pos;
	hDAKey	*key;

	max = h->sort->n;
	key = h->sort->key;
	for ( i = pos = 0; i < max; i++ )
	{
		// Suffix length.
		len = key[i]->len - key[i]->depth + 1;

		if ( key[i]->rec )
		{
			// Apply byte boundary.
			if ( pos > TAIL_MAX - len - h->mask )
				return	DA_EMAX;
			pos = ( pos + len + h->mask ) & ~h->mask;
			if ( pos > TAIL_MAX - key[i]->rec )
				return	DA_EMAX;
			pos += ( h->dic->rec > key[i]->rec ) ? h->dic->rec : key[i]->rec;
		}
		else
		{
			// Ignore byte boundary because there are no records.
			if ( pos > TAIL_MAX - len )
				return	DA_EMAX;
			pos += len;
		}
	}

	// Allocate memory.
	return	DAInf_ResizeTail( h, pos );
}

// Enumerate suffixes.
static	void	DAInf_LineTail( hDAInf h )
{
	int		i, max, len;
	hDAKey	*key;

	DADic_SetMask( h->dic, 0 );

	max = h->sort->n;
	key = h->sort->key;
	for ( i = 0; i < max; i++ )
	{
		// Suffix length.
		len = key[i]->len - key[i]->depth + 1;

		// Consider byte boundary of records.
		if ( key[i]->rec )
			h->pos = ( ( h->pos + len + h->mask ) & ~h->mask ) - len;

		// Arrange a suffix and a record.
		DADic_WStr( h->dic, h->pos, key[i]->s + key[i]->depth );
		DADic_WPos( h->dic, key[i]->idx, h->pos );
		DADic_WRec( h->dic, key[i]->idx, 0 );

		h->pos += len + key[i]->rec;
	}
}

// Unify common suffixes.
static	void	DAInf_UnifyTail( hDAInf h )
{
	int		i, max, len, ct, nbit = 0;
	hDAKey	*key;

	// Sort suffixes in descending order.
	DASuffix_Sort( h->sort );

	// Generate a mask.
	while ( h->ntail >> nbit )
		nbit++;
	DADic_SetMask( h->dic, 31 - nbit );

	// Arrange suffixes but some unifications are canceled because of a mask.
	max = h->sort->n;
	key = h->sort->key;
	for ( i = ct = 0; i < max; i++ )
	{
		// Suffix length.
		len = key[i]->len - key[i]->depth + 1;

		// Number of keys unified is limited.
		if ( key[i]->unify && key[i]->rec && ct == h->dic->lmask )
			key[i]->unify = 0;

		// If a key is not unified.
		if ( !key[i]->unify )
		{
			// Modify the next position.
			h->pos += h->dic->rec * ct;
			ct = 0;

			// Consider byte boundary of records.
			if ( DAInf_NeedBoundary( h, i ) )
				h->pos = ( h->pos + len + h->mask ) & ~h->mask;
			else
				h->pos += len;

			// Write a suffix.
			DADic_WStr( h->dic, h->pos - len, key[i]->s + key[i]->depth );
		}

		// Write the position of suffix and record.
		DADic_WPos( h->dic, key[i]->idx, h->pos - len );
		DADic_WRec( h->dic, key[i]->idx, ct );

		// Count the number of keys which have records.
		if ( key[i]->rec )
			ct++;
	}

	// The last record.
	h->pos += h->dic->rec * ct;
}

// Build TAIL.
static	int		DAInf_BuildTail( hDAInf h )
{
	int		ret;

	// Calculate the record period of arrangement.
	DAInf_RecordPeriod( h );

	// Allocate memory to TAIL.
	if ( ( ret = DAInf_TotalTail( h ) ) != DA_OK )
		return	ret;

	// Arrange suffixes and records.
	if ( DAInf_NeedUnify( h ) )
		DAInf_UnifyTail( h );
	else
		DAInf_LineTail( h );

	// Reduce the size of TAIL.
	if ( ( ret = DAInf_ReduceTail( h ) ) != DA_OK )
		return	ret;

	return	DA_OK;
}


// Construction of a dictionary.


// Set byte boundary of records.
static	int		DADic_Boundary( hDADic h, int boundary )
{
	int		i;
	unsigned	x, n = 0;

	// Confirm the range of byte boundary.
	if ( boundary == 0 )
		boundary = BOUND_MIN;
	else if ( boundary < BOUND_MIN  || boundary > BOUND_MAX )
		return	DA_EARG;

	// Confirm the boundary is 2^n.
	x = ( unsigned )boundary;
	for ( i = 0; i < 32; i++ )
		n += x = ( x >> 1 ) | ( x << 31 );
	if ( ~n )
		return	DA_EARG;

	h->boundary = boundary;

	return	DA_OK;
}

// Edit a dictionary.
static	int		DADic_Edit( hDADic h, hDASort sort )
{
	int		ret;
	hDAInf	inf;

	// Create temporary information to build a dictionary.
	if ( ( inf = DAInf_Create( h, sort ) ) == NULL )
		return	DA_EMEM;

	// Build the root, BC and TAIL in order.
	if ( ( ret = DAInf_Root( inf ) ) == DA_OK &&
		 ( ret = DAInf_BuildBC( inf ) ) == DA_OK &&
		 ( ret = DAInf_ReduceBC( inf ) ) == DA_OK )
	{
		DAInf_Revise( inf );
		ret = DAInf_BuildTail( inf );
	}

	// Destroy the information.
	DAInf_Delete( inf );

	return	ret;
}

// Construction of a dictionary.
static	int		DADic_Construct( hDADic h, hDASet set, int boundary )
{
	int		ret;
	hDASort		sort;

	// Set the boundary.
	if ( ( ret = DADic_Boundary( h, boundary ) ) != DA_OK )
		return	ret;

	// Sort a keyset.
	if ( ( ret = DASort_Open( &sort, set ) ) != DA_OK )
		return	ret;

	// Build a dictionary.
	h->nkey = set->n;
	h->maxlen = sort->depth;
	ret = DADic_Edit( h, sort );

	// Destroy a sorted keyset.
	DASort_Close( sort );

	return	ret;
}


// Retrieval.


// Search a key which matches an input string.
static	void	*DADic_ExactMatch( hDADic h, const char *key )
{
	int		idx;
	char	*tail;

	// Confirm arcs.
	idx = DADic_Base( h, IDX_ROOT ) ^ ( unsigned char )*key;
	while ( !DADic_Leaf( h, idx ) )
	{
		if ( DADic_Check( h, idx ) != ( unsigned char )*key )
			return	NULL;
		idx = DADic_Base( h, idx ) ^ ( unsigned char )*++key;
	}

	// Confirm suffixes.
	tail = DADic_Str( h, DADic_Pos( h, idx ) );
	if ( ( tail = DAStr_Match( tail, key ) ) == NULL )
		return	NULL;

	// Start position of a record.
	return	tail + h->rec * DADic_Rec( h, idx );
}

// Search keys match the first part of an input string.
static	void	*DADic_PrefixMatch( hDADic h, const char **s, int *idx )
{
	int		leaf, flag = 0;
	char	*tail = NULL;

	// Adjust the start position.
	if ( *idx == IDX_ROOT )
		--*s;

	while ( !DADic_Leaf( h, *idx ) )
	{
		// Confirm an arc with the end marker.
		if ( *++*s != '\0' )
		{
			leaf = DADic_Base( h, *idx ) ^ '\0';
			if ( DADic_Leaf( h, leaf ) )
			{
				tail = DADic_Str( h, DADic_Pos( h, leaf ) );
				if ( ( flag = ( *tail++ == '\0' ) ) )
					tail += h->rec * DADic_Rec( h, leaf );
			}
		}

		// Confirm an arc.
		*idx = DADic_Base( h, *idx ) ^ ( unsigned char )**s;
		if ( !DADic_Leaf( h, *idx ) )
		{
			if ( DADic_Check( h, *idx ) != ( unsigned char )**s )
			{
				*idx = -1;
				return	flag ? tail : NULL;
			}
		}

		// Find a prefix.
		if ( flag )
			return	tail;
	}

	// Confirm a suffix.
	tail = DADic_Str( h, DADic_Pos( h, *idx ) );
	tail = DAStr_Prefix( tail, s );
	if ( tail != NULL )
		tail += h->rec * DADic_Rec( h, *idx );
	*idx = -1;

	// Start position of a record.
	return	tail;
}

// Search keys which appear in an input string.
static	void	*DADic_InfixMatch( hDADic h, const char **start,
								   const char **s, int *idx )
{
	void	*rec;

	// Prefix searches by sliding the start position.
	while ( *idx == -1 || ( rec = DADic_PrefixMatch( h, s, idx ) ) == NULL )
	{
		if ( **start == '\0' )
			return	NULL;

		*s = ++*start;
		*idx = IDX_ROOT;
	}

	return	rec;
}


// Dictionary header.


// Confirm a header.
static	int		DAHead_Check( hDAHead h )
{
	// Confirm an identifer.
	if ( memcmp( h->str, HEAD_STR, sizeof( h->str ) ) )
		return	DA_EFMT;

	// Confirm the version is compatible or not.
	if ( h->version < DA_COMPAT )
		return	DA_EVER;

	return	DA_OK;
}

// Read a header.
static	int		DAHead_Read( hDAHead h, FILE *fp )
{
	if ( fread( h, sizeof( *h ), 1, fp ) != 1 )
		return	DA_EIO;

	return	DAHead_Check( h );
}

// Write a header.
static	int		DAHead_Write( hDAHead h, FILE *fp )
{
	if ( fwrite( h, sizeof( *h ), 1, fp ) != 1 )
		return	DA_EIO;

	return	DA_OK;
}


// Input and output of a dictionary.


// Restore a dictionary from a header.
static	int		DADic_Restore( hDADic h, hDAHead head )
{
	int		ret;

	// Dictionary information.
	h->nkey = head->nkey;
	h->maxlen = head->maxlen;
	DADic_SetMask( h, head->nbit );
	h->boundary = head->boundary;
	h->rec = head->rec;

	// Allocate memory.
	if ( ( ret = DADic_ResizeBC( h, head->nbc ) ) != DA_OK ||
		 ( ret = DADic_ResizeTail( h, head->ntail ) ) != DA_OK )
		return	ret;

	return	DA_OK;
}

// Generate a header.
static	void	DADic_Head( hDADic h, hDAHead head )
{
	memset( head, 0, sizeof( *head ) );

	// Identifier.
	memcpy( head->str, HEAD_STR, sizeof( head->str ) );
	head->version = DA_VERSION;

	// Dictionary information.
	head->nbc = h->nbc;
	head->ntail = h->ntail;
	head->nkey = h->nkey;
	head->maxlen = h->maxlen;
	head->nbit = h->nbit;
	head->boundary = h->boundary;
	head->rec = h->rec;
}

// Read a dictionary.
static	int		DADic_Read( hDADic h, FILE *fp )
{
	int		ret;
	DAHead	head;

	// Read a header and restore a dictionary.
	if ( ( ret = DAHead_Read( &head, fp ) ) != DA_OK )
		return	ret;
	if ( ( ret = DADic_Restore( h, &head ) ) != DA_OK )
		return	ret;

	// Read a dictionary body.
	if ( fread( h->bc, sizeof( *h->bc ) * h->nbc, 1, fp ) != 1 )
		return	DA_EIO;
	else if ( h->ntail && fread( h->tail, h->ntail, 1, fp ) != 1 )
		return	DA_EIO;

	return	DA_OK;
}

// Load a dictionary.
static	int		DADic_Load( hDADic h, const char *path )
{
	int		ret;
	FILE	*fp;

	if ( ( fp = fopen( path, "rb" ) ) == NULL )
		return	DA_EIO;

	ret = DADic_Read( h, fp );

	fclose( fp );

	return	ret;
}

// Write a dictionary.
static	int		DADic_Write( hDADic h, FILE *fp )
{
	int		ret;
	DAHead	head;

	// Write a header.
	DADic_Head( h, &head );
	if ( ( ret = DAHead_Write( &head, fp ) ) != DA_OK )
		return	ret;

	// Write a dictionary body.
	if ( fwrite( h->bc, sizeof( *h->bc ) * h->nbc, 1, fp ) != 1 )
		return	DA_EIO;
	else if ( h->ntail && fwrite( h->tail, h->ntail, 1, fp ) != 1 )
		return	DA_EIO;

	return	DA_OK;
}


// Enumerate registered keys.


// Initialize.
static	void	DAEnum_Init( hDAEnum h )
{
	memset( h, 0, sizeof( *h ) );

	h->idx = NULL;
	h->key = NULL;
}

// Create.
static	hDAEnum		DAEnum_Create( void )
{
	hDAEnum		h;

	if ( ( h = ( hDAEnum )malloc( sizeof( *h ) ) ) != NULL )
		DAEnum_Init( h );

	return	h;
}

// Clear.
static	void	DAEnum_Finish( hDAEnum h )
{
	if ( h->idx != NULL )
		free( h->idx );
	if ( h->key != NULL )
		free( h->key );
}

// Destroy.
static	void	DAEnum_Delete( hDAEnum h )
{
	DAEnum_Finish( h );
	free( h );
}

// Allocate memory for enumeration.
static	int		DAEnum_Alloc( hDAEnum h, hDADic dic )
{
	int		num;

	// Memory for indexes and prefixes.
	num = dic->maxlen + 1;
	h->idx = ( int * )malloc( sizeof( *h->idx ) * ( num + 1 ) );
	h->key = ( char * )malloc( num );
	if ( h->idx == NULL || h->key == NULL )
		return	DA_EMEM;

	h->idx[0] = IDX_ROOT;
	h->key[0] = '\0';

	return	DA_OK;
}

// Calculate the index of the next node.
static	void	DAEnum_Next( hDAEnum h, hDADic dic, int depth )
{
	int		base;

	base = DADic_Base( dic, h->idx[depth] );
	h->idx[ depth + 1 ] = base ^ ( unsigned char )h->key[depth];
}

// Check the previous node.
static	int		DAEnum_Check( hDAEnum h, hDADic dic, int depth )
{
	int		c;

	c = DADic_Check( dic, h->idx[ depth + 1 ] );

	return	 ( unsigned char )h->key[depth] == c;
}

// Enumerate registered keys.
static	int		DAEnum_Scan( hDAEnum h, hDADic dic, void *arg, fDACall call )
{
	int		depth = 0, ret = DA_OK;
	char	*tail, *p;

	do
	{
		DAEnum_Next( h, dic, depth );
		if ( DADic_Leaf( dic, h->idx[ depth + 1 ] ) )
		{
			// Confirm TAIL.
			tail = DADic_Str( dic, DADic_Pos( dic, h->idx[ depth + 1 ] ) );
			if ( *tail == h->key[depth] )
			{
				// Copy a key and calculate the position of record.
				p = h->key + depth;
				do
					*p++ = *tail;
				while ( *tail++ != '\0' );
				tail += dic->rec * DADic_Rec( dic, h->idx[ depth + 1 ] );
				if ( ( ret = call( h->key, tail, arg ) ) != DA_OK )
					break;
			}
		}
		else if ( DAEnum_Check( h, dic, depth ) )
		{
			h->key[ ++depth ] = '\0';
			continue;
		}

		// Confirm arcs with every letter.
		if ( ++h->key[depth] == '\0' )
		{
			if ( depth-- )
				h->key[depth]++;
		}
	}	while ( depth >= 0 );

	return	ret;
}

// Enumerate registered keys.
static	int		DADic_EnumKey( hDADic h, void *arg, fDACall call )
{
	int		ret;
	hDAEnum		en;

	if ( ( en = DAEnum_Create() ) == NULL )
		return	DA_EMEM;

	if ( ( ret = DAEnum_Alloc( en, h ) ) == DA_OK )
		ret = DAEnum_Scan( en, h, arg, call );

	DAEnum_Delete( en );

	return	ret;
}


// External interfaces.


// Build a dictionary from a keyset.
// The 3rd argument specifies the boundary of records, in other words,
// all records are arranged on the specified byte boundary.
int		DADic_Build( hDADic *h, hDASet set, int boundary )
{
	int		ret;

	if ( h == NULL )
		return	DA_EHDL;
	*h = NULL;
	if ( set == NULL )
		return	DA_EARG;

	if ( ( *h = DADic_Create() ) == NULL )
		return	DA_EMEM;

	if ( ( ret = DADic_Construct( *h, set, boundary ) ) != DA_OK )
	{
		DADic_Delete( *h );
		*h = NULL;
	}

	return	ret;
}

// Load a dictionary from a file.
int		DADic_Open( hDADic *h, const char *path )
{
	int		ret;

	if ( h == NULL )
		return	DA_EHDL;
	*h = NULL;
	if ( path == NULL )
		return	DA_EARG;

	if ( ( *h = DADic_Create() ) == NULL )
		return	DA_EHDL;

	if ( ( ret = DADic_Load( *h, path ) ) != DA_OK )
	{
		DADic_Delete( *h );
		*h = NULL;
	}

	return	ret;
}

// Destroy a dictionary.
int		DADic_Close( hDADic h )
{
	if ( h == NULL )
		return	DA_EHDL;

	DADic_Delete( h );

	return	DA_OK;
}

// Save a dictionary to a file.
int		DADic_Save( hDADic h, const char *path )
{
	int		ret;
	FILE	*fp;

	if ( h == NULL )
		return	DA_EHDL;
	else if ( path == NULL )
		return	DA_EARG;

	if ( ( fp = fopen( path, "wb" ) ) == NULL )
		return	DA_EIO;

	ret = DADic_Write( h, fp );

	fclose( fp );

	return	ret;
}

// Get an information of a dictionary.
int		DADic_Status( hDADic h, hDAStat st )
{
	if ( h == NULL )
		return	DA_EHDL;
	else if ( st == NULL )
		return	DA_EARG;

	st->nbc = h->nbc;
	st->ntail = h->ntail;
	st->size = h->nbc * sizeof( *h->bc ) + h->ntail;
	st->nkey = h->nkey;
	st->maxlen = h->maxlen;
	st->boundary = h->boundary;

	return	DA_OK;
}

// Call a callback function for each key in a dictionary.
// The 2nd argument will be passed to the callback function.
int		DADic_Enum( hDADic h, void *arg, fDACall call )
{
	if ( h == NULL )
		return	DA_EHDL;
	else if ( call == NULL )
		return	DA_EARG;

	return	DADic_EnumKey( h, arg, call );
}

// Search a key which equals to an input string.
// If such a key exists, this function returns a pointer to its record.
// In case the key doesn't have a record, non-NULL pointer will be returned.
// If not, this function returns NULL.
void	*DADic_Search( hDADic h, const char *key )
{
	if ( h == NULL || key == NULL )
		return	NULL;

	return	DADic_ExactMatch( h, key );
}

// Search keys which match a prefix of an input string.
// Each call of this function returns only one key even if there are more than
// one keys to be returned, so this function should be called repeatedly until
// it returns NULL.
// In the 1st call, a pointer to a string and a pointer to an index
// zero-cleared must be passed, then this function overwrites the pointers.
void	*DADic_Prefix( hDADic h, const char **s, int *idx )
{
	if ( h == NULL || s == NULL || *s == NULL || idx == NULL )
		return	NULL;
	else if ( *idx < 0 || *idx >= h->nbc )
		return	NULL;

	return	DADic_PrefixMatch( h, s, idx );
}

// Search keys which appears in an input string.
// Similar to DADic_Prefix, each call of this function returns only one key
// even if there are more than one keys to be returned, so this function should
// be called repeatedly until it returns NULL.
// In the 1st call, 2 pointers to a string and a pointer to an index
// zero-cleared must be passed, then this function overwrites the pointers.
void	*DADic_Infix( hDADic h, const char **start, const char **s, int *idx )
{
	if ( h == NULL || start == NULL || s == NULL || idx == NULL )
		return	NULL;
	else if ( *start == NULL || *s == NULL )
		return	NULL;
	else if ( *idx >= h->nbc )
		return	NULL;

	return	DADic_InfixMatch( h, start, s, idx );
}


//
// Error messages.
//


// Return an error message.
#define		DAErr_ReturnMsg( s )\
	{ static const char msg[] = s; return msg; }

// Get an error message from an error code.
const char	*DAErr_String( int err )
{
	switch ( err )
	{
	case	DA_OK:
		DAErr_ReturnMsg( "No error" );
	case	DA_EHDL:
		DAErr_ReturnMsg( "Invalid handle" );
	case	DA_EMEM:
		DAErr_ReturnMsg( "Memory allocation error" );
	case	DA_EIO:
		DAErr_ReturnMsg( "I/O error" );
	case	DA_EARG:
		DAErr_ReturnMsg( "Invalid argument" );
	case	DA_EFMT:
		DAErr_ReturnMsg( "Invalid format" );
	case	DA_EMAX:
		DAErr_ReturnMsg( "Too large" );
	case	DA_EVER:
		DAErr_ReturnMsg( "Version error" );
	}

	DAErr_ReturnMsg( "Unknown error" );
}
